package com.atguigu.binaryTree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PreOrderIn {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(1);
        root.left=new TreeNode(2);
        root.right=new TreeNode(3);
        root.left.left=new TreeNode(4);
        root.left.right=new TreeNode(5);
        root.right.left=new TreeNode(6);
        root.right.right=new TreeNode(7);
        preOrderInStack(root);
        System.out.println();
        inOrderInStack(root);
        System.out.println();
        postOrderInStack(root);
    }
    public static void postOrderInStack(TreeNode root){
        if(root==null) return;
        Stack<TreeNode> stack=new Stack<>();
        Stack<TreeNode> help=new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node=stack.pop();
            help.push(node);
            if(node.left!=null){
                stack.push(node.left);
            }
            if(node.right!=null){
                stack.push(node.right);
            }
        }
        while(!help.isEmpty()){
            System.out.print(help.pop().val+" ");
        }
    }
    public static void inOrderInStack(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);
        root= root.left;
        List<TreeNode> list=new ArrayList<>();
        while(!stack.isEmpty()||root!=null){
            if(root!=null){
                stack.push(root);
                root=root.left;
            }else{
                root=stack.pop();
                System.out.print(root.val+" ");
                root=root.right;
            }
        }
    }
    //非遍历形式完成前序遍历
    public static void preOrderInStack(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node=stack.pop();
            if(node.right!=null){
                stack.push(node.right);
            }
            if(node.left!=null){
                stack.push(node.left);
            }
            System.out.print(node.val+" ");
        }
    }
}
